{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>x</code> ，如果 <code>x</code> 是一个回文整数，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>121</code> 是回文，而 <code>123</code> 不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 121\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = -121\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 10\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>从右向左读, 为 01 。因此它不是一个回文数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-2<sup>31</sup>&nbsp;&lt;= x &lt;= 2<sup>31</sup>&nbsp;- 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能不将整数转为字符串来解决这个问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-number](https://leetcode.cn/problems/palindrome-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-number](https://leetcode.cn/problems/palindrome-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['121', '-121', '10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not head.next:\n",
    "            return True\n",
    "        pf = pl = head\n",
    "        l = []\n",
    "        flag = 1\n",
    "        while pf.next:\n",
    "            l.append(pl.val)\n",
    "            pl = pl.next\n",
    "            pf = pf.next.next\n",
    "            if not pf:\n",
    "                flag = 0\n",
    "                break\n",
    "        if flag:\n",
    "            pl = pl.next\n",
    "        while pl:\n",
    "            if pl.val != l.pop():\n",
    "                return False\n",
    "            pl = pl.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "\n",
    "        values = []\n",
    "\n",
    "        cur = head\n",
    "        while cur:\n",
    "            values.append(cur.val)\n",
    "            cur = cur.next\n",
    "        \n",
    "        print(values)\n",
    "        return values == values[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        cur = head\n",
    "        temp = []\n",
    "        while cur != None:\n",
    "            temp.append(str(cur.val))\n",
    "            cur = cur.next\n",
    "        if temp[::] == temp[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head: return True\n",
    "        def rev(head):\n",
    "            if head.next is None: return head\n",
    "            dummy = ListNode(-1,head)\n",
    "            rev_tail = head\n",
    "            while (to_rev := rev_tail.next) is not None:\n",
    "                nxt = to_rev.next\n",
    "                rev_tail.next = nxt\n",
    "                origin_head = dummy.next\n",
    "                dummy.next = to_rev\n",
    "                to_rev.next = origin_head\n",
    "            return dummy.next\n",
    "        def pp(node_input):\n",
    "            node = node_input\n",
    "            res = []\n",
    "            while node:\n",
    "                res.append(node.val)\n",
    "                node = node.next\n",
    "            print('，'.join(map(str,res)))\n",
    "        # find half\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        pp(fast)\n",
    "        pp(slow)\n",
    "        rev_head = rev(slow)\n",
    "        cur,rev_cur = head,rev_head \n",
    "        pp(cur)\n",
    "        pp(rev_cur)\n",
    "        while rev_cur and cur:\n",
    "            if rev_cur.val != cur.val: return False\n",
    "            rev_cur,cur = rev_cur.next,cur.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        \n",
    "        node = head\n",
    "        c = 0\n",
    "        while node:\n",
    "            c += 1\n",
    "            node = node.next\n",
    "        \n",
    "        sign = c & 1\n",
    "        c >>= 1\n",
    "        for _ in range(c):\n",
    "            head.next.prev = head\n",
    "            head = head.next\n",
    "            del head.prev.next\n",
    "        if sign:\n",
    "            node = head\n",
    "            for _ in range(c):\n",
    "                head = head.next\n",
    "                node = node.prev\n",
    "                if head.val != node.val:\n",
    "                    return False\n",
    "            return True\n",
    "        else:\n",
    "            node = head.prev\n",
    "            for _ in range(c-1):\n",
    "                if head.val != node.val:\n",
    "                    return False\n",
    "                head = head.next\n",
    "                node = node.prev\n",
    "            \n",
    "            return head.val == node.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        fast=head\n",
    "        slow=head\n",
    "        while fast and fast.next:\n",
    "            slow=slow.next\n",
    "            fast=fast.next.next\n",
    "        if not slow:\n",
    "            return True\n",
    "        last = ListNode(slow.val)\n",
    "        cover = slow\n",
    "        while slow and slow.next:\n",
    "            slow = slow.next\n",
    "            cover = ListNode(slow.val)\n",
    "            cover.next = last\n",
    "            last = cover\n",
    "        while cover:\n",
    "            if cover.val!=head.val:\n",
    "                return False\n",
    "            cover=cover.next\n",
    "            head=head.next\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if head is None:\n",
    "            return True\n",
    "            \n",
    "        ptr, slow, fast = ListNode(), ListNode(), ListNode()\n",
    "        ptr.next, slow.next, fast.next = head, head, head\n",
    "        while fast is not None and fast.next is not None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            # reverse left part\n",
    "            next = ptr.next\n",
    "            ptr.next = ListNode(slow.val)\n",
    "            ptr.next.next = next \n",
    "\n",
    "        if fast is None:\n",
    "            ptr.next = ptr.next.next\n",
    "\n",
    "        while ptr.next is not None and slow.next is not None:\n",
    "            ptr = ptr.next\n",
    "            slow = slow.next\n",
    "            if ptr.val != slow.val:\n",
    "                return False\n",
    "        \n",
    "        return ptr.next is not None or slow.next is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        value = {}\n",
    "        count = 0\n",
    "        while head:\n",
    "            \n",
    "            value.update({count : head.val})\n",
    "            head = head.next\n",
    "            count +=1\n",
    "        #print(value)\n",
    "        left, right = 0, (count-1)\n",
    "        while left <= right:\n",
    "            if value.get(left) != value.get(right):\n",
    "                #print(left, right)\n",
    "                return False\n",
    "            left +=1\n",
    "            right -=1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        # reverse node\n",
    "        rev = None\n",
    "        curr = head\n",
    "        while(curr):\n",
    "            temp = ListNode(curr.val)\n",
    "            temp.next = rev\n",
    "            rev = temp\n",
    "            curr=curr.next\n",
    "\n",
    "        while(head):\n",
    "            if(head.val != rev.val):\n",
    "                return False\n",
    "            head = head.next\n",
    "            rev = rev.next\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        L = None\n",
    "        p=head\n",
    "        while p is not None:\n",
    "            q=ListNode(val=p.val)\n",
    "            q.next=L \n",
    "            L=q\n",
    "            p=p.next\n",
    "        p=head\n",
    "        while p and L:\n",
    "            if p.val != L.val:\n",
    "                return False\n",
    "            else:\n",
    "                p=p.next\n",
    "                L=L.next\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def reverse():\n",
    "            nh = None \n",
    "            cur = head\n",
    "            while cur:\n",
    "                ln = ListNode(cur.val)\n",
    "                ln.next = nh\n",
    "                nh = ln\n",
    "                cur = cur.next\n",
    "            return nh \n",
    "        nh = reverse()\n",
    "        c1, c2 = head, nh\n",
    "        while c1 and c2:\n",
    "            if c1.val != c2.val:\n",
    "                return False\n",
    "            c1, c2 = c1.next, c2.next\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def judge(a,b):\n",
    "            if a and b:\n",
    "                if a.val==b.val:\n",
    "                    return judge(a.next,b.next)\n",
    "            elif a==None and b==None:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        if not head: return True\n",
    "        if not head.next: return True\n",
    "        first=ListNode(head.val)\n",
    "        f=first\n",
    "        second=head.next\n",
    "        while first and second:\n",
    "            # print(first,'\\n',second)\n",
    "            if judge(first,second):\n",
    "                return True\n",
    "            f=ListNode(second.val)\n",
    "            f.next=first\n",
    "            second=second.next\n",
    "            if second and judge(first,second):\n",
    "                return True\n",
    "            first=f\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        slow, fast, last = head, head.next, None\n",
    "        while fast.next and fast.next.next:\n",
    "            tmp = slow.next\n",
    "            slow.next = last if last else None\n",
    "            last = slow\n",
    "            slow = tmp\n",
    "            fast = fast.next.next\n",
    "        middle = slow.next.next if fast.next else slow.next # 区分链表长度为奇数偶数的情况,middle为后半段的开始\n",
    "        slow.next = last #完成前半段翻转\n",
    "        while middle:\n",
    "            if slow.val != middle.val:\n",
    "                return False\n",
    "            slow, middle = slow.next, middle.next\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def find_half(head):\n",
    "            slow,fast=head,head\n",
    "            while fast.next and fast.next.next:\n",
    "                slow=slow.next\n",
    "                fast=fast.next.next\n",
    "            return slow\n",
    "        def reverseList(head):\n",
    "            prev=None\n",
    "            cur=head\n",
    "            while cur:\n",
    "                temp=cur.next\n",
    "                cur.next=prev\n",
    "                prev=cur\n",
    "                cur=temp\n",
    "            return prev\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        half_p=find_half(head)\n",
    "        after_r=reverseList(half_p.next)\n",
    "        p=head\n",
    "        q=after_r\n",
    "        while q:\n",
    "            if p.val!=q.val:\n",
    "                return False\n",
    "            p=p.next\n",
    "            q=q.next\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        ans=[]\n",
    "        p=head\n",
    "        while p:\n",
    "            ans.append(p.val)\n",
    "            p=p.next\n",
    "        print(ans)\n",
    "\n",
    "        if ans==ans[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next :\n",
    "            return True\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        while head:\n",
    "            ans.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        return self.palindromeFind(ans, 0)\n",
    "            \n",
    "    def palindromeFind(self, list, i):\n",
    "        if len(list)-1-i == i or (len(list)-1-i == i+1 and list[len(list)-1-i] == list[i]):\n",
    "            return True\n",
    "        elif len(list)-1-i<i or list[i] != list[len(list)-1-i]:\n",
    "            return False\n",
    "        return self.palindromeFind(list, i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        slow, fast = dummy, dummy\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        head1 = head\n",
    "        # 奇数情况\n",
    "        if fast.next:\n",
    "            head2 = slow.next.next\n",
    "            slow.next = None\n",
    "        else:\n",
    "            head2 = slow.next\n",
    "            slow.next = None\n",
    "        # 反转链表\n",
    "        head3 = self.reverse(head2)\n",
    "        # 比较 head1 和 head3\n",
    "        return self.isSame(head1, head3)\n",
    "    \n",
    "    def reverse(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        pre = None\n",
    "        while head:\n",
    "            nex = head.next\n",
    "            head.next = pre\n",
    "            pre = head\n",
    "            head = nex\n",
    "        return pre\n",
    "    \n",
    "    def isSame(self, head1, head2):\n",
    "        if not head1 and not head2:\n",
    "            return True\n",
    "        if not head1 or not head2:\n",
    "            return False\n",
    "        if head1.val != head2.val:\n",
    "            return False\n",
    "        return self.isSame(head1.next, head2.next)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head: return True\n",
    "\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "        right = self.reverse(slow)\n",
    "        while head and right:\n",
    "            if head.val != right.val:\n",
    "                return False\n",
    "            head = head.next\n",
    "            right = right.next\n",
    "        return True\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head.next: return head\n",
    "\n",
    "        cur = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next: return True\n",
    "        po = ListNode(0)\n",
    "        po.next=head\n",
    "        slow = fast = po\n",
    "        while fast and fast.next:\n",
    "            slow =slow.next\n",
    "            fast=fast.next.next\n",
    "        node =head\n",
    "        slow = self.rever(slow.next)\n",
    "        while slow:\n",
    "            if slow.val != node.val:\n",
    "                return False\n",
    "            slow =slow.next\n",
    "            node = node.next\n",
    "        return True\n",
    "\n",
    "    def rever(self,node):\n",
    "        if not node.next:\n",
    "            return node\n",
    "        head=self.rever(node.next)\n",
    "        node.next.next=node\n",
    "        node.next = None\n",
    "        return head\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        lst = [head.val]\n",
    "        while head.next:\n",
    "            lst.append(head.next.val)\n",
    "            head.next = head.next.next\n",
    "\n",
    "        def fun(lst,i,j):\n",
    "            if j-i<=0:\n",
    "                return True\n",
    "            else:\n",
    "                return fun(lst,i+1,j-1) and (lst[i]==lst[j])\n",
    "        \n",
    "        return fun(lst,0,len(lst)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindromeSub(self, node, pos):\n",
    "        if pos < (self.m-1)//2:\n",
    "            flag = self.isPalindromeSub(node.next, pos+1)\n",
    "            flag = flag and node.val == self.q.val\n",
    "            self.q = self.q.next\n",
    "            return flag\n",
    "        else:\n",
    "            self.q = node.next\n",
    "            if self.m%2 == 1:\n",
    "                return True\n",
    "            else:\n",
    "                flag = node.val == self.q.val\n",
    "                self.q = self.q.next\n",
    "                return flag\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        p = head\n",
    "        self.m = 0\n",
    "        while p:\n",
    "            self.m += 1\n",
    "            p = p.next\n",
    "        \n",
    "        self.q = head\n",
    "        flag = self.isPalindromeSub(head, 0)\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        if not head.next:\n",
    "            return True\n",
    "        # 快慢指针\n",
    "        cur1 = head\n",
    "        cur2 = head\n",
    "        while cur2.next and cur2.next.next:\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next.next\n",
    "        self.head1=cur1\n",
    "        if cur2.next:\n",
    "            self.head2 = cur1.next\n",
    "        else:\n",
    "            self.head2 = cur1\n",
    "        #  倒序遍历查看是否相等\n",
    "        return self.reverse(head)\n",
    "    def reverse(self,head):\n",
    "        if head is self.head1:\n",
    "            if self.head2 and head.val ==self.head2.val:\n",
    "                self.head2 = self.head2.next\n",
    "                return True\n",
    "            return False\n",
    "        next_is = self.reverse(head.next)\n",
    "        if next_is:\n",
    "            if self.head2.val ==head.val:\n",
    "                self.head2 = self.head2.next\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        \n",
    "        if head.next.next == None:\n",
    "            return head.val == head.next.val\n",
    "        \n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "        right = self.reverse(slow.next)\n",
    "        left = head\n",
    "        while right:\n",
    "            if right.val != left.val:\n",
    "                return False\n",
    "\n",
    "            right = right.next\n",
    "            left = left.next\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        cur = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return cur\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def _base(self, slow, fast):\n",
    "        if fast.next is None:\n",
    "            return True, slow.next\n",
    "        if fast.next.next is None:\n",
    "            return slow.val == slow.next.val, slow.next.next\n",
    "        res = self._base(slow.next, fast.next.next)\n",
    "        ret = res[0]\n",
    "        if ret is False:\n",
    "            return False, None\n",
    "        return slow.val == res[1].val, res[1].next\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or head and head.next is None:\n",
    "            return True\n",
    "\n",
    "        return self._base(head, head)[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def length(self, head):\n",
    "        len = 0\n",
    "        while head != None:\n",
    "            len += 1\n",
    "            head = head.next\n",
    "        return len\n",
    "\n",
    "    def isPalindromeRecurse(self, head, len):\n",
    "        if head == None or len <= 0:\n",
    "            return head, True\n",
    "        elif len == 1:\n",
    "            return head.next, True\n",
    "        \n",
    "        node, res = self.isPalindromeRecurse(head.next, len - 2)\n",
    "\n",
    "        if not res or node == None:\n",
    "            return node, res\n",
    "\n",
    "        res = head.val == node.val\n",
    "        node = node.next\n",
    "\n",
    "        return node, res\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        len = self.length(head)\n",
    "        node, res = self.isPalindromeRecurse(head, len)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        \n",
    "        # 队列，n，n\n",
    "        # s = deque()\n",
    "        # while head:\n",
    "        #     s.append(head.val)\n",
    "        #     head = head.next\n",
    "        # l = len(s)\n",
    "        # if l == 1:return True\n",
    "        # if l == 2:return s[0] == s[1]\n",
    "        # while l>1:\n",
    "        #     l -= 2\n",
    "        #     a,b = s.popleft(),s.pop()\n",
    "        #     if a!=b:return False\n",
    "        # return True\n",
    "\n",
    "        # 快慢指针 + 递归反转 n，1\n",
    "        # 1.具体来说，先通过快慢指针找到链表中点\n",
    "        # 2.然后使用递归反转将后一半链表反转\n",
    "        # 3.再对链表前半部分和后半部分逐节点进行比较\n",
    "        # 4.最后恢复后半链表，输出结果\n",
    "        if not head or not head.next:return True \n",
    "        # 1.\n",
    "        slow,fast = head,head.next\n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            if fast:\n",
    "                fast = fast.next\n",
    "                slow = slow.next\n",
    "            else:\n",
    "                break\n",
    "        # slow对应中点，如果链表长为奇数，那么slow就是中点节点，否则slow是前一半的最后一个节点\n",
    "        # 2.\n",
    "        def rever(node):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            p = rever(node.next)\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return p\n",
    "        # 3.\n",
    "        r = rever(slow.next)\n",
    "        slow.next = None\n",
    "        rh = r\n",
    "        p = head\n",
    "        while r:\n",
    "            if p.val != r.val:\n",
    "                return False\n",
    "            p = p.next\n",
    "            r = r.next\n",
    "        # 4.\n",
    "        v = rever(rh)\n",
    "        slow.next = v\n",
    "        return True\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        p = head\n",
    "        length = 0\n",
    "        while p:\n",
    "            p = p.next\n",
    "            length += 1\n",
    "        \n",
    "        mid = length // 2\n",
    "        if length % 2 == 1:\n",
    "            mid += 1\n",
    "        mid_node = head\n",
    "        for _ in range(mid):\n",
    "            mid_node = mid_node.next\n",
    "        \n",
    "        mid_node = self.reverse(mid_node)\n",
    "        slow, fast = head, mid_node\n",
    "        while fast:\n",
    "            if slow.val != fast.val:\n",
    "                return False\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    def reverse(self, head):\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        last = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        p = head\n",
    "        length = 0\n",
    "        while p:\n",
    "            p = p.next\n",
    "            length += 1\n",
    "        \n",
    "        mid = length // 2\n",
    "        if length % 2 == 1:\n",
    "            mid += 1\n",
    "        mid_node = head\n",
    "        for _ in range(mid):\n",
    "            mid_node = mid_node.next\n",
    "        \n",
    "        _, flag = self.check(head, mid_node)\n",
    "        return flag\n",
    "        \n",
    "    def check(self, l1, l2):\n",
    "        if not l2:\n",
    "            return l1, True\n",
    "        if not l2.next:\n",
    "            flag = l2.val == l1.val\n",
    "            return l1.next, flag\n",
    "        l1, last = self.check(l1, l2.next)\n",
    "        return l1.next, last and l1.val == l2.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def reverse(cur,pre):\n",
    "            if not cur:\n",
    "                return pre\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            return reverse(tmp,cur)\n",
    "\n",
    "        if not head:\n",
    "            return True\n",
    "        if head.next is None:\n",
    "            return True\n",
    "        if head.next.next is None:\n",
    "            return head.val == head.next.val\n",
    "        slow = fast = head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        slow.next = reverse(slow.next,None)\n",
    "        p1 = head\n",
    "        p2 = slow.next\n",
    "        while p2:\n",
    "            if p1.val != p2.val:\n",
    "                return False\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool: \n",
    "        def findMid(head: ListNode):\n",
    "            slow, fast = head, head.next.next\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            res = slow.next\n",
    "            slow.next = None\n",
    "            return res\n",
    "\n",
    "        def reverse(head: ListNode):\n",
    "            if not head or not head.next:\n",
    "                return head\n",
    "            tail = reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return tail\n",
    "\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        mid = findMid(head)\n",
    "        revMid = reverse(mid)\n",
    "        p = head\n",
    "        while revMid and p:\n",
    "            if revMid.val != p.val:\n",
    "                return False\n",
    "            else:\n",
    "                revMid = revMid.next\n",
    "                p = p.next\n",
    "        return True\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next :\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        rev = self.reverse(slow)\n",
    "        p = head\n",
    "        while rev:\n",
    "            if p.val != rev.val:\n",
    "                return False\n",
    "            else:\n",
    "                p = p.next\n",
    "                rev = rev.next\n",
    "        return True\n",
    "    def reverse(self, head:ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        res = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Result:\n",
    "    def __init__(self, node,length):\n",
    "        self.node = node\n",
    "        self.res = True\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def getLength(head):\n",
    "            res = 0\n",
    "            while head:\n",
    "                res += 1\n",
    "                head = head.next\n",
    "            return res\n",
    "        \n",
    "        def isPalindromeRecurse(head, length):\n",
    "            if not head or length <=0:\n",
    "                return Result(head, True) # 到中间位置了，并且长度为偶数\n",
    "            \n",
    "            elif length == 1:   # 到中间位置并且长度为奇数，返回后半部分第一个\n",
    "                return Result(head.next, True)\n",
    "\n",
    "            else: \n",
    "                res = isPalindromeRecurse(head.next, length-2)\n",
    "                if not res.res or res.node == None:\n",
    "                    return res\n",
    "\n",
    "                res.res = (head.val == res.node.val)\n",
    "                res.node = res.node.next\n",
    "                return res \n",
    "\n",
    "        length = getLength(head)\n",
    "        res = isPalindromeRecurse(head, length)\n",
    "        return res.res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        s_p = f_p = head\n",
    "        while True:\n",
    "            if not f_p:\n",
    "                self.odd_flag = False\n",
    "                break\n",
    "            elif f_p.next:\n",
    "                s_p = s_p.next\n",
    "                f_p = f_p.next.next\n",
    "            else:\n",
    "                self.odd_flag = True\n",
    "                break\n",
    "        mid_node = s_p\n",
    "        node = head\n",
    "        def palindrome(node,mid_node):\n",
    "            if node.next == mid_node:\n",
    "                if self.odd_flag:\n",
    "                    return node.val == mid_node.next.val, mid_node.next.next\n",
    "                else:\n",
    "                    return node.val == mid_node.val,mid_node.next\n",
    "            flag, re_node = palindrome(node.next,mid_node)\n",
    "            return flag and re_node.val == node.val, re_node.next\n",
    "        flag, re_node = palindrome(node,mid_node)\n",
    "        return flag\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        s_p = f_p = head\n",
    "        while True:\n",
    "            if not f_p:\n",
    "                self.odd_flag = False\n",
    "                break\n",
    "            elif f_p.next:\n",
    "                s_p = s_p.next\n",
    "                f_p = f_p.next.next\n",
    "            else:\n",
    "                self.odd_flag = True\n",
    "                break\n",
    "        mid_node = s_p\n",
    "        node = head\n",
    "        def palindrome(node,mid_node):\n",
    "            if node.next == mid_node:\n",
    "                if self.odd_flag:\n",
    "                    return node.val == mid_node.next.val, mid_node.next.next\n",
    "                else:\n",
    "                    return node.val == mid_node.val,mid_node.next\n",
    "            flag, re_node = palindrome(node.next,mid_node)\n",
    "            return flag and re_node.val == node.val, re_node.next\n",
    "        flag, re_node = palindrome(node,mid_node)\n",
    "        return flag\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "            \n",
    "        return self.func([head],head)\n",
    "        \n",
    "\n",
    "\n",
    "    def func(self, p, head):\n",
    "\n",
    "        if not head:\n",
    "            return True\n",
    "\n",
    "        if self.func(p, head.next) == False:\n",
    "            return False\n",
    "\n",
    "\n",
    "        if head:\n",
    "            if p[0].val != head.val:\n",
    "                return False\n",
    "            else:\n",
    "                p[0] = p[0].next\n",
    "                return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "            \n",
    "        return self.func([head],head)\n",
    "        \n",
    "\n",
    "\n",
    "    def func(self, p, q):\n",
    "\n",
    "        if not q:\n",
    "            return True\n",
    "\n",
    "        if self.func(p, q.next) == False:\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "        if p[0].val != q.val:\n",
    "            return False\n",
    "        else:\n",
    "            p[0] = p[0].next\n",
    "            return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def f(node: ListNode):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            res = f(node.next)\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return res\n",
    "        fast = slow = head\n",
    "        while fast and fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        rev = f(slow.next) if slow else None\n",
    "        while head and rev:\n",
    "            if head.val == rev.val:\n",
    "                head = head.next\n",
    "                rev = rev.next\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    front = None\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front = head\n",
    "        return self.checkPalindrome(head)\n",
    "\n",
    "    def checkPalindrome(self, head):\n",
    "        if not head:\n",
    "            return True\n",
    "        b_p = self.checkPalindrome(head.next) and head.val == self.front.val\n",
    "        self.front = self.front.next\n",
    "        return b_p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.flag=True\n",
    "        self.root=head\n",
    "        self.dfs(head)\n",
    "        return self.flag\n",
    "    def dfs(self,head):\n",
    "        if not head:\n",
    "            return ;\n",
    "        self.dfs(head.next)\n",
    "\n",
    "        if head.val!=self.root.val:\n",
    "            self.flag=False\n",
    "        self.root=self.root.next\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.arr1 = []\n",
    "        self.arr2 = []\n",
    "        self.preorder(head)\n",
    "        self.postorder(head)\n",
    "        return self.arr1 == self.arr2\n",
    "    def preorder(self,head):\n",
    "        if not head:\n",
    "            return None\n",
    "        self.arr1.append(head.val)\n",
    "        self.preorder(head.next)\n",
    "    def postorder(self,head):\n",
    "        if not head:\n",
    "            return None\n",
    "        self.postorder(head.next)\n",
    "        self.arr2.append(head.val)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head):\n",
    "        arr = (self.preorder(head))\n",
    "        left,right = 0,len(arr) - 1\n",
    "        while left < right:\n",
    "            if arr[left] != arr[right]:\n",
    "                return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return True\n",
    "    \n",
    "    def preorder(self,head):\n",
    "        if not head:\n",
    "            return []\n",
    "        return [head.val] + self.preorder(head.next)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        node1 = head\n",
    "        node2 = head\n",
    "        return self._search(node1) == self._search2(node2)\n",
    "\n",
    "    def _search(self, head):\n",
    "        if not head:\n",
    "            return \"\"\n",
    "        ans = self._search(head.next)\n",
    "        return ans + str(head.val)\n",
    "\n",
    "    def _search2(self, head):\n",
    "        if not head:\n",
    "            return \"\"\n",
    "        ans = str(head.val)\n",
    "        return ans + self._search2(head.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head):\n",
    "        return self.preorder(head) == self.preorder(head)[::-1]\n",
    "    \n",
    "    def preorder(self,head):\n",
    "        if not head:\n",
    "            return []\n",
    "        return [head.val] + self.preorder(head.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front_pointer = head\n",
    "        \n",
    "        def recursively_check(current_node=head):\n",
    "            if current_node is not None:\n",
    "                if not recursively_check(current_node.next):\n",
    "                    return False\n",
    "                if self.front_pointer.val != current_node.val:\n",
    "                    return False\n",
    "                self.front_pointer = self.front_pointer.next\n",
    "            return True\n",
    "\n",
    "        return recursively_check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front = head\n",
    "        def recursive(cur):\n",
    "            \"\"\"判断是否是回文链表\"\"\"\n",
    "            if cur is None:\n",
    "                return True\n",
    "            if not recursive(cur.next):\n",
    "                return False\n",
    "            elif self.front.val != cur.val:\n",
    "                return False\n",
    "            else:\n",
    "                self.front = self.front.next\n",
    "                return True\n",
    "        return recursive(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def flip(self, head):\n",
    "        if not head.next:\n",
    "            return head\n",
    "\n",
    "        new_head = self.flip(head.next)\n",
    "        # print(head.val)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return new_head\n",
    "        \n",
    "    def list_show(self, head):\n",
    "        res = []\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head = head.next\n",
    "        return res\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        res = True\n",
    "        origin_list = self.list_show(head)\n",
    "        if not head:\n",
    "            return res\n",
    "        elif not head.next:\n",
    "            return res\n",
    "        elif not head.next.next:\n",
    "            if head.val == head.next.val:\n",
    "                return res\n",
    "            else:\n",
    "                res = False\n",
    "                return res\n",
    "\n",
    "        fliped_head = self.flip(head)\n",
    "        fliped_list = self.list_show(fliped_head)\n",
    "        for i in range(len(origin_list)):\n",
    "            if origin_list[i] != fliped_list[i]:\n",
    "                res = False\n",
    "                break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front_pointer=head\n",
    "        def recursively_check(current_node=head):\n",
    "            if current_node is not None:\n",
    "                if not recursively_check(current_node.next):\n",
    "                    return False\n",
    "                if self.front_pointer.val!=current_node.val:\n",
    "                    return False\n",
    "                self.front_pointer=self.front_pointer.next\n",
    "            return True\n",
    "        return recursively_check()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # self.front_pointer = head\n",
    "\n",
    "        # def recursively_check(current_node=head):\n",
    "        #     if current_node is not None:\n",
    "        #         if not recursively_check(current_node.next):\n",
    "        #             return False\n",
    "        #         if self.front_pointer.val != current_node.val:\n",
    "        #             return False\n",
    "        #         self.front_pointer = self.front_pointer.next\n",
    "        #     return True\n",
    "\n",
    "        # return recursively_check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        # 递归函数外的指针\n",
    "        self.front_pointer = head\n",
    "        \n",
    "        # 递归函数\n",
    "        def recursively_check(cur = head):\n",
    "            if cur:\n",
    "                # 反向迭代节点\n",
    "                if not recursively_check(cur.next):\n",
    "                    return False\n",
    "                if self.front_pointer.val != cur.val:\n",
    "                    return False\n",
    "                # 递归函数外的变量向前迭代\n",
    "                self.front_pointer = self.front_pointer.next\n",
    "            return True\n",
    "        \n",
    "        return recursively_check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.front = head\n",
    "        def check(node):\n",
    "            if not node:\n",
    "                return True\n",
    "            if not check(node.next):\n",
    "                return False\n",
    "            if node.val != self.front.val:\n",
    "                return False\n",
    "            self.front = self.front.next\n",
    "            return True\n",
    "        return check(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: 'ListNode') -> 'bool':\n",
    "        if not head:\n",
    "            return True\n",
    "        s = []\n",
    "        while head:\n",
    "            s.append(str(head.val))\n",
    "            head = head.next\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "\n",
    "        if not (head and head.next):\n",
    "            return True\n",
    "        \n",
    "        p = ListNode(-1)\n",
    "        p.next, slow, fast = head, p, p\n",
    "        \n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        cur, pre = slow.next, None\n",
    "        \n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        \n",
    "        first, second = p.next, pre\n",
    "        while second:\n",
    "            if first.val != second.val:\n",
    "                return False\n",
    "            first, second = first.next, second.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "\n",
    "'''一种复制链表的方法'''\n",
    "# class Solution:\n",
    "#     def isPalindrome(self, head: ListNode) -> bool:\n",
    "         \n",
    "#         cur = head\n",
    "#         value = [] ## 空列表用来存储链表中的值\n",
    "#         while cur:\n",
    "#             value.append(cur.val)\n",
    "#             cur = cur.next\n",
    "#         return value == value[::-1] ## 翻转列表，如果与原列表相等，则为回文链表\n",
    "\n",
    "\n",
    "\n",
    "'''一种反转链表后半部分进行比较的方法'''\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        \n",
    "        if not head: ## 判空\n",
    "            return True\n",
    "        \n",
    "        elif not head.next: ## 判断是否只有一个元素\n",
    "            return True\n",
    "        \n",
    "        else: ## 快慢指针\n",
    "            slow = head\n",
    "            fast = head.next\n",
    "\n",
    "            while fast and fast.next: ## 得到后半部分\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "\n",
    "            post_part_head = slow.next\n",
    "\n",
    "            ## 双指针翻转后半部分\n",
    "            pre = None\n",
    "            cur = post_part_head\n",
    "\n",
    "            while cur:\n",
    "                temp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = temp\n",
    "\n",
    "            ## 判断后半部分和前半部分是否相同\n",
    "            pre_part_cur = head\n",
    "            post_part_cur = pre\n",
    "\n",
    "            while pre_part_cur and post_part_cur:\n",
    "                if pre_part_cur.val != post_part_cur.val:\n",
    "                    return False\n",
    "                pre_part_cur = pre_part_cur.next\n",
    "                post_part_cur = post_part_cur.next\n",
    "                \n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        fast = head \n",
    "        slow = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        fast = None\n",
    "        while slow:\n",
    "            temp = slow.next\n",
    "            slow.next = fast\n",
    "            fast = slow\n",
    "            slow = temp\n",
    "        while fast:\n",
    "            if fast.val != head.val:\n",
    "                return False\n",
    "            else:\n",
    "                fast = fast.next\n",
    "                head = head.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        length = 0\n",
    "        p = head\n",
    "        while p:\n",
    "            length += 1\n",
    "            p=p.next\n",
    "        if length < 2:\n",
    "            return True\n",
    "\n",
    "        p = head\n",
    "        for _ in range((length+1)//2-1):\n",
    "            p = p.next\n",
    "        \n",
    "        self.pNode(head)\n",
    "\n",
    "        cur = p.next\n",
    "        p.next = None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = p.next\n",
    "            p.next = cur\n",
    "            cur = tmp\n",
    "\n",
    "        self.pNode(head)\n",
    "        \n",
    "        p=p.next\n",
    "        self.pNode(p)\n",
    "        while p:\n",
    "            if p.val != head.val:\n",
    "                return False\n",
    "            p=p.next\n",
    "            head = head.next\n",
    "\n",
    "        return True\n",
    "    def pNode(self, node):\n",
    "        tt = node\n",
    "        res = []\n",
    "        while tt:\n",
    "            res.append(tt.val)\n",
    "            tt=tt.next\n",
    "        print(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        a = []\n",
    "        b = []\n",
    "        head_ = head\n",
    "        while head:\n",
    "            a.append(str(head.val))\n",
    "            head = head.next\n",
    "        \n",
    "        prev = None\n",
    "        cur = head_\n",
    "        while cur:\n",
    "            temp  = cur.next\n",
    "            cur.next = prev\n",
    "            prev = cur\n",
    "            cur = temp\n",
    "        \n",
    "        while prev:\n",
    "            b.append(str(prev.val))\n",
    "            prev = prev.next\n",
    "        a = \"\".join(a) \n",
    "        b = \"\".join(b)\n",
    "        if a == b:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        s, ptr = [], head\n",
    "        while ptr:\n",
    "            s.append(str(ptr.val))\n",
    "            ptr = ptr.next\n",
    "        return ''.join(s) == ''.join(s[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:    \n",
    "        if not head: return True \n",
    "        vals = []\n",
    "        j = 0\n",
    "        while head:\n",
    "            vals.append([j,head.val])\n",
    "            head = head.next\n",
    "            j += 1\n",
    "        l = len(vals)\n",
    "        mid = l // 2 + 1\n",
    "        for i in range(mid):\n",
    "            if vals[i][1] != vals[l-1-i][1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "\n",
    "\n",
    "\n",
    "        # 快慢指针\n",
    "        slow  = head\n",
    "        fast = head\n",
    "        pre = None\n",
    "\n",
    "        while fast and fast.next:\n",
    "            node = slow.next\n",
    "            if pre:\n",
    "                slow.next = pre\n",
    "            \n",
    "            pre = slow\n",
    "            slow = node\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        if fast:\n",
    "            slow = slow.next\n",
    "        \n",
    "        while slow:\n",
    "            if slow.val != pre.val:\n",
    "                return False\n",
    "\n",
    "            slow = slow.next\n",
    "            pre = pre.next\n",
    "        \n",
    "        return True\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        p = head\n",
    "        cnt = 0\n",
    "        while p is not None:\n",
    "            p = p.next\n",
    "            cnt += 1\n",
    "        if cnt == 0 or cnt == 1:\n",
    "            return True\n",
    "        elif cnt == 2:\n",
    "            if head.val == head.next.val:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            p = head\n",
    "            q = head.next\n",
    "            r = q.next \n",
    "            p.next = None\n",
    "            n = (cnt-1) // 2\n",
    "            for i in range(n):\n",
    "                q.next = p\n",
    "                p = q\n",
    "                q = r\n",
    "                r = r.next\n",
    "            if cnt % 2 == 1:\n",
    "                p = p.next\n",
    "            while p is not None and q is not None and p.val == q.val:\n",
    "                p = p.next\n",
    "                q = q.next\n",
    "            if p is None and q is None:\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        # 保证长度大于1，方便一刀两段\n",
    "        if not head.next: return True\n",
    "\n",
    "        # 遍历一遍得长度\n",
    "        # -------------\n",
    "        l = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            l += 1\n",
    "        # ---------------\n",
    "        \n",
    "\n",
    "        # 根据长度反转前面一半的链表\n",
    "        # -------------------------\n",
    "        pre = None\n",
    "        cur = head\n",
    "        i = 0\n",
    "        while l//2 != i:\n",
    "            nxt =cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "            i += 1\n",
    "        # -----------------------\n",
    "        # 长度为奇数，中间的数不用比较\n",
    "        if l % 2 == 1: cur = cur.next\n",
    "\n",
    "\n",
    "        # 一一对照即可\n",
    "        while cur and pre:\n",
    "            if cur.val != pre.val:\n",
    "                return False\n",
    "            cur = cur.next\n",
    "            pre = pre.next\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        lst1, lst2 = [], []\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            lst1.append(cur.val)\n",
    "            next = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next\n",
    "        cur = pre\n",
    "        while cur:\n",
    "            lst2.append(cur.val)\n",
    "            cur = cur.next\n",
    "        print(lst1, lst2)\n",
    "        return lst1 == lst2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        last = None\n",
    "        while(cur):\n",
    "            nxt = cur.next\n",
    "            cur.next = None\n",
    "            if last:\n",
    "                cur.next = last\n",
    "            last = cur\n",
    "            cur = nxt\n",
    "        return last\n",
    "\n",
    "    def check_list(self, list1: ListNode, list2: ListNode) -> bool:\n",
    "        if list1 is None and list2 is None:\n",
    "            return True\n",
    "        return list1.val == list2.val and self.check_list(list1.next, list2.next)\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "        if not head.next.next:\n",
    "            return head.val == head.next.val\n",
    "        fast = head.next\n",
    "        slow = head\n",
    "        second = None\n",
    "        while(True):\n",
    "            if not fast.next:\n",
    "                second = slow.next\n",
    "                slow.next = None\n",
    "                break\n",
    "            if not fast.next.next:\n",
    "                slow = slow.next\n",
    "                second = ListNode(slow.val)\n",
    "                second.next = slow.next\n",
    "                slow.next = None\n",
    "                break\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        new_head = self.reverse(second)\n",
    "        return self.check_list(head, new_head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        def reverse(head):\n",
    "            pre, cur = None, head\n",
    "            while cur:\n",
    "                third = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = third\n",
    "            return pre\n",
    "\n",
    "        if not head:\n",
    "            return True\n",
    "        # 快慢指针寻找后半段链表\n",
    "        pre, slow, fast = None, head, head\n",
    "        while fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        if fast:\n",
    "            pre = slow\n",
    "            slow = slow.next\n",
    "        # 翻转后半段\n",
    "        last = right = reverse(slow)\n",
    "        # 判断\n",
    "        left = head\n",
    "        while left and right:\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        # 恢复原链表\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse_partial(self, start, end):\n",
    "        # 区域翻转(start-end之间的部分) 返回start-end区间中的头尾节点 inplace\n",
    "        pre, cur = start, start.next\n",
    "        dummy = cur  # 尾节点\n",
    "        while cur != end:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        start.next = pre\n",
    "        dummy.next = cur  # 尾节点连接\n",
    "        return pre, dummy\n",
    "\n",
    "    def middle_node(self, head):\n",
    "        slow = fast = head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    "\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head:\n",
    "            return head\n",
    "        if not head.next:\n",
    "            return True\n",
    "        mid_pre = self.middle_node(head)\n",
    "        pre, dummy = self.reverse_partial(mid_pre, None)\n",
    "        # cur = mid_pre\n",
    "        mid_pre.next = None\n",
    "        \n",
    "        # print(head, pre)\n",
    "        while pre:\n",
    "            if head.val != pre.val:\n",
    "                return False\n",
    "            head = head.next\n",
    "            pre = pre.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        if head == None or head.next == None:\n",
    "            return True\n",
    "        fast, slow = head, head\n",
    "        while fast.next != None and fast.next.next != None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        pre, cur = None, slow.next\n",
    "        while cur != None:\n",
    "            nex = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nex\n",
    "        while pre != None:\n",
    "            if pre.val != head.val:\n",
    "                return False\n",
    "            pre = pre.next\n",
    "            head = head.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        slow = head\n",
    "        fast = head \n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        cur = slow.next\n",
    "        pre = None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre \n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        while pre:\n",
    "            if head.val != pre.val:\n",
    "                return False\n",
    "            pre = pre.next\n",
    "            head = head.next \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        l=[]\n",
    "        while head:\n",
    "            l.append(head.val)\n",
    "            head=head.next\n",
    "        n=len(l)\n",
    "        for i in range(len(l)):\n",
    "            if l[i]==l[n-1]:\n",
    "                if(n-1-i==1 or n-1==i):return True\n",
    "                n=n-1\n",
    "                continue\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        first_half_end = self.end_of_first_healf(head)\n",
    "        second_half_start = self.reverse_list(first_half_end.next)\n",
    "        res = True\n",
    "        first_position = head\n",
    "        second_position = second_half_start\n",
    "        while res and first_position and second_position:\n",
    "            if first_position.val != second_position.val:\n",
    "                res = False\n",
    "            first_position = first_position.next\n",
    "            second_position = second_position.next\n",
    "        first_half_end.next = self.end_of_first_healf(second_half_start)\n",
    "        return res\n",
    "        \n",
    "    \n",
    "    def end_of_first_healf(self, head):\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast and fast.next and fast.next.next :\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        return slow\n",
    "    def reverse_list(self, head):\n",
    "        previous = None\n",
    "        current = head\n",
    "        while current:\n",
    "            next_node = current.next\n",
    "            current.next = previous\n",
    "            previous = current\n",
    "            current = next_node\n",
    "        return previous\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        def reverseListNode(node):\n",
    "            pre_node = None\n",
    "            while node:\n",
    "                next_node = node.next\n",
    "                node.next = pre_node\n",
    "                pre_node = node\n",
    "                node = next_node\n",
    "            return pre_node\n",
    "\n",
    "        node_length = 0\n",
    "        cur_node = head\n",
    "        while cur_node:\n",
    "            node_length += 1\n",
    "            cur_node = cur_node.next\n",
    "        if node_length == 1:\n",
    "            return True\n",
    "        move_step = node_length // 2\n",
    "        cur_node = head\n",
    "        for i in range(move_step):\n",
    "            cur_node = cur_node.next\n",
    "        left_end_node = cur_node\n",
    "        if node_length % 2 == 1:\n",
    "            cur_node = cur_node.next\n",
    "        reverse_right_head = reverseListNode(cur_node)\n",
    "        cur_reverse_head = reverse_right_head\n",
    "        cur_node = head\n",
    "        res = True\n",
    "        while cur_reverse_head:\n",
    "            if cur_reverse_head.val != cur_node.val:\n",
    "                res = False\n",
    "                break\n",
    "            cur_node = cur_node.next\n",
    "            cur_reverse_head = cur_reverse_head.next\n",
    "        left_end_node.next = reverseListNode(reverse_right_head)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        temp = []\n",
    "        while head:\n",
    "            temp.append(head.val)\n",
    "            head = head.next\n",
    "        return temp[::-1] == temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if head is None:\n",
    "            return True\n",
    "\n",
    "        # 找到前半部分链表的尾节点并反转后半部分链表\n",
    "        first_half_end = self.end_of_first_half(head)\n",
    "        second_half_start = self.reverse_list(first_half_end.next)\n",
    "\n",
    "        # 判断是否回文\n",
    "        result = True\n",
    "        first_position = head\n",
    "        second_position = second_half_start\n",
    "        while result and second_position is not None:\n",
    "            if first_position.val != second_position.val:\n",
    "                result = False\n",
    "            first_position = first_position.next\n",
    "            second_position = second_position.next\n",
    "\n",
    "        # 还原链表并返回结果\n",
    "        first_half_end.next = self.reverse_list(second_half_start)\n",
    "        return result    \n",
    "\n",
    "    def end_of_first_half(self, head):\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast.next is not None and fast.next.next is not None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        return slow\n",
    "\n",
    "    def reverse_list(self, head):\n",
    "        previous = None\n",
    "        current = head\n",
    "        while current is not None:\n",
    "            next_node = current.next\n",
    "            current.next = previous\n",
    "            previous = current\n",
    "            current = next_node\n",
    "        return previous\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None, Pre=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "        self.pre = pre\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if head.next is None: return True\n",
    "\n",
    "        pre_p,cur_p=head,head.next\n",
    "        while cur_p:\n",
    "            cur_p.pre=pre_p\n",
    "            pre_p=cur_p\n",
    "            cur_p=cur_p.next\n",
    "        cur_p=head\n",
    "        while cur_p!=pre_p and cur_p.next!=pre_p:\n",
    "            if cur_p.val==pre_p.val:\n",
    "                cur_p=cur_p.next\n",
    "                pre_p=pre_p.pre\n",
    "            else:\n",
    "                return False\n",
    "        if cur_p.val==pre_p.val:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def reverseList(l):\n",
    "            if not l or not l.next:\n",
    "                return l\n",
    "            pre = None\n",
    "            while l:\n",
    "                tmp = l.next\n",
    "                l.next = pre\n",
    "                pre = l \n",
    "                l = tmp\n",
    "            return pre\n",
    "        slow,fast = head,head\n",
    "        while fast.next and fast.next.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        tmpHead = slow.next\n",
    "        slow.next = None\n",
    "        nhead = reverseList(tmpHead)\n",
    "        nheadbak = nhead\n",
    "        while head and nhead:\n",
    "            if head.val!=nhead.val:\n",
    "                slow.next = reverseList(nheadbak)\n",
    "                return False\n",
    "            head = head.next\n",
    "            nhead = nhead.next\n",
    "        result = True\n",
    "        if  head and not head.next:\n",
    "            result = True\n",
    "        elif not head and not nhead:\n",
    "            result = True\n",
    "        else:\n",
    "            result = False\n",
    "        slow.next = reverseList(nheadbak)\n",
    "        print(head)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "# # solution pass\n",
    "# class Solution:\n",
    "#     def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "#         res = []\n",
    "#         p = head\n",
    "#         while p:\n",
    "#             res.append(p.val)\n",
    "#             p = p.next\n",
    "#         if res == res[::-1]:\n",
    "#             return True\n",
    "#         else:\n",
    "#             return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        '''\n",
    "        Step 1: find middle position\n",
    "        Step 2: reverse the right part of the linkedlist\n",
    "        Step 3: isPalindrome determination\n",
    "        '''\n",
    "        fast = slow = head\n",
    "        while fast != None and fast.next != None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        if fast != None:\n",
    "            slow = slow.next\n",
    "\n",
    "        # pre = None\n",
    "        # curr = slow\n",
    "        # while curr:\n",
    "        #     next = curr.next\n",
    "        #     curr.next = pre\n",
    "        #     pre = curr\n",
    "        #     curr = next\n",
    "        \n",
    "        # reverse function\n",
    "        def reverse(head):\n",
    "            pre = None\n",
    "            curr = head\n",
    "            while curr:\n",
    "                next = curr.next\n",
    "                curr.next = pre\n",
    "                pre = curr\n",
    "                curr = next\n",
    "            return pre\n",
    "        \n",
    "\n",
    "        right = q = reverse(slow)\n",
    "        left = head\n",
    "        # right = pre\n",
    "        while right != None:\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        # left is p\n",
    "        # recover original data\n",
    "        left.next = reverse(q)\n",
    "        print(head)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head:\n",
    "            return False\n",
    "        \n",
    "        # go through the linked list and take note of values\n",
    "        register = {}\n",
    "        N = 0\n",
    "        while head:\n",
    "            register[N] = head\n",
    "            head = head.next\n",
    "            N = N + 1\n",
    "\n",
    "        N = len(register)\n",
    "            \n",
    "        for l in range(0, int(N/2)):\n",
    "            r = N - l - 1\n",
    "            if register[l].val != register[r].val:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head:\n",
    "            return True\n",
    "        prev = {}\n",
    "        tail = head\n",
    "        p = None\n",
    "        while tail:\n",
    "            prev[tail]=p\n",
    "            p = tail\n",
    "            tail = tail.next\n",
    "        tail = p\n",
    "        node = head\n",
    "        while node!=tail and tail.next!=node:\n",
    "            if node.val!=tail.val:\n",
    "                return False\n",
    "            node = node.next\n",
    "            tail = prev[tail]\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        \n",
    "        if head.next is None:\n",
    "            return True\n",
    "        \n",
    "        data_dict = {}\n",
    "        i = 0\n",
    "        p = head\n",
    "        while p is not None:\n",
    "            data_dict[i] = p.val\n",
    "            i += 1\n",
    "            p = p.next\n",
    "\n",
    "        i -= 1\n",
    "        p = head\n",
    "        while p is not None:\n",
    "            if data_dict[i] != p.val:\n",
    "                return False\n",
    "            i -= 1\n",
    "            p = p.next\n",
    "\n",
    "        return True\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  _global_pointer = None\n",
    "  def _check(self, head):\n",
    "    if(head == None):\n",
    "      return True\n",
    "\n",
    "    if(not self._check(head.next)):\n",
    "      return False\n",
    "    if(self._global_pointer.val != head.val):\n",
    "      return False\n",
    "\n",
    "    self._global_pointer = self._global_pointer.next\n",
    "    return True\n",
    "\n",
    "\n",
    "  def isPalindrome(self, head):\n",
    "    if(head == None):\n",
    "      return True\n",
    "    self._global_pointer = head\n",
    "    return self._check(head.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    left = None\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.left = head\n",
    "        return self.traverse(head)\n",
    "\n",
    "    def traverse(self, right):\n",
    "        if right is None:\n",
    "            return True\n",
    "        res = self.traverse(right.next)\n",
    "        res = res and (self.left.val == right.val)\n",
    "        self.left = self.left.next\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        cur,pre1,pre2=head,ListNode(0),ListNode(0)\n",
    "        rep1,rep2=pre1,pre2\n",
    "        while cur:\n",
    "            node1,node2=ListNode(cur.val),ListNode(cur.val)\n",
    "            pre1.next,cur,pre1,pre2.next,pre2=node1,cur.next,node1,node2,node2\n",
    "        curr,prev=rep1.next,None\n",
    "        while curr:\n",
    "            curr.next,prev,curr=prev,curr,curr.next\n",
    "        while prev:\n",
    "            if prev.val!=rep2.next.val:\n",
    "                return False\n",
    "            else:\n",
    "                prev,rep2=prev.next,rep2.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from numpy import *\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        vals = []\n",
    "        current_node = head\n",
    "        while current_node is not None:\n",
    "            vals.append(current_node.val)\n",
    "            current_node = current_node.next\n",
    "        return vals == vals[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        nums = []\n",
    "        while head:\n",
    "            nums.append(head.val)\n",
    "            head = head.next\n",
    "        r1 = np.array(nums)\n",
    "        r2 = np.array(nums[::-1])\n",
    "        if (r1 == r2).all():\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.tmp = None\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if head == None:\n",
    "            return True\n",
    "        if self.tmp == None:\n",
    "            self.tmp = head\n",
    "        flag = True\n",
    "        if head.next:\n",
    "            flag &= self.isPalindrome(head.next)\n",
    "        flag &= (head.val == self.tmp.val)\n",
    "        self.tmp = self.tmp.next\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        lst, tsl = [], []\n",
    "        self.traverse(lst, tsl, head)\n",
    "        return lst == tsl\n",
    "\n",
    "    def traverse(self, lst, tsl, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        lst.append(node.val)\n",
    "        self.traverse(lst, tsl, node.next)\n",
    "        tsl.append(node.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# class Solution:\n",
    "#     def isPalindrome(self, head: ListNode) -> bool:\n",
    "#         if not head:\n",
    "#             return True\n",
    "#         p = q = head\n",
    "#         while p.next and q and q.next:\n",
    "#             p = p.next\n",
    "#             q = q.next.next\n",
    "#\n",
    "#         mid = p\n",
    "#         q = p.next\n",
    "#         while p and q:\n",
    "#             tmp = q.next\n",
    "#             q.next = p\n",
    "#             p = q\n",
    "#             q = tmp\n",
    "#\n",
    "#         while head != mid:\n",
    "#             if head.val != p.val:\n",
    "#                 return False\n",
    "#             head = head.next\n",
    "#             p = p.next\n",
    "#         return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        left = head\n",
    "\n",
    "        def _is_palindrome(root):\n",
    "            if not root:\n",
    "                return\n",
    "            yield from _is_palindrome(root.next)\n",
    "            nonlocal left\n",
    "            if root == left:\n",
    "                yield True\n",
    "            if left.val != root.val:\n",
    "                yield False\n",
    "            left = left.next\n",
    "            if left == root:\n",
    "                yield True\n",
    "        return next(_is_palindrome(head), True)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        h=ListNode(0)\n",
    "        h2=h\n",
    "        head1=head\n",
    "        while(head1!=None):\n",
    "            temp=ListNode(head1.val)\n",
    "            head1=head1.next\n",
    "            temp.next=None\n",
    "            h.next=temp\n",
    "            h=temp\n",
    "\n",
    "        m=self.reserve(head)\n",
    "        while(m!=None):\n",
    "            if h2.next.val!=m.val:\n",
    "                return False\n",
    "            else:\n",
    "                h2=h2.next\n",
    "                m=m.next\n",
    "        return True\n",
    "            \n",
    "\n",
    "\n",
    "    def reserve(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None:\n",
    "            return head\n",
    "        last=self.reserve(head.next)\n",
    "        head.next.next=head\n",
    "        head.next=None\n",
    "        return last\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        if head.next is None:\n",
    "            return True\n",
    "\n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "        if fast is not None:\n",
    "            slow = slow.next\n",
    "\n",
    "        left = head\n",
    "        right = self.reverse(slow)\n",
    "\n",
    "        while right:\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "    def reverse(self, node):\n",
    "        if node.next is None:\n",
    "            return node\n",
    "\n",
    "        last_node = self.reverse(node.next)\n",
    "\n",
    "        node.next.next = node\n",
    "        node.next = None\n",
    "\n",
    "        return last_node\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        ##反转后半部们列表，然后两个指针判断\n",
    "        if head is None: return False\n",
    "        if head.next is None: return True\n",
    "        count = 0\n",
    "        curr = head\n",
    "        while curr is not None:\n",
    "            count += 1\n",
    "            curr = curr.next\n",
    "        if count % 2 == 0:\n",
    "            count = count // 2\n",
    "        else:\n",
    "            count = (count + 1) // 2\n",
    "        curr = head\n",
    "        for i in range(count):\n",
    "            curr = curr.next\n",
    "        last = self.reverse(curr)\n",
    "        while last is not None:\n",
    "            if last.val != head.val:\n",
    "                return False\n",
    "            last = last.next\n",
    "            head = head.next\n",
    "        return True\n",
    "    \n",
    "    def reverse(self, head):\n",
    "        if head.next is None:\n",
    "            return head\n",
    "        last = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ret = True\n",
    "        self.p2 = None\n",
    "        self.len = 0\n",
    "\n",
    "    def fun(self, p1, n):\n",
    "        if n == self.len // 2:\n",
    "            self.p2 = p1.next\n",
    "            if self.len % 2 == 1:\n",
    "                self.p2 = self.p2.next\n",
    "            if p1.val != self.p2.val:\n",
    "                self.ret = False\n",
    "            return\n",
    "        #\n",
    "        self.fun(p1.next, n+1)\n",
    "        if self.ret == False:\n",
    "            return\n",
    "        #\n",
    "        self.p2 = self.p2.next\n",
    "        if p1.val != self.p2.val:\n",
    "            self.ret = False\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        p1 = head\n",
    "        self.p2 = head\n",
    "        #\n",
    "        if head == None or head.next == None:\n",
    "            return True\n",
    "        #\n",
    "        tmp = head\n",
    "        while tmp != None:\n",
    "            self.len += 1\n",
    "            tmp = tmp.next\n",
    "        #\n",
    "        self.fun(p1, 1)\n",
    "        #\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sss(self, deep, node, length) -> (bool, ListNode):\n",
    "        if deep == length//2:\n",
    "            # print('deep:', deep, node.val, node.next.val)\n",
    "            if length %2 == 1:\n",
    "                if node.val == node.next.val:\n",
    "                    return True, node.next.next\n",
    "                else:\n",
    "                    return False, None\n",
    "            else:\n",
    "                return True, node.next\n",
    "            \n",
    "        is_palindrome, next_node = self.sss(deep+1, node.next, length)\n",
    "        # print(is_palindrome, node.val, next_node)\n",
    "        if is_palindrome and node.val == next_node.val:\n",
    "            return True, next_node.next\n",
    "        return False, None\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        length = 0\n",
    "        root = head\n",
    "        while(root.next is not None):\n",
    "            length += 1\n",
    "            root = root.next\n",
    "        if length == 0:\n",
    "            return True\n",
    "        res, _ = self.sss(0, head, length)\n",
    "        return res \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.font = None\n",
    "    \n",
    "    def reverseTopN(self, node, n):\n",
    "        if n == 1:\n",
    "            self.font = node.next\n",
    "            return node\n",
    "        \n",
    "        res = self.reverseTopN(node.next, n-1)\n",
    "        node.next.next = node\n",
    "        node.next = self.font\n",
    "        return res\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        cnt, cp = 0, head\n",
    "        while cp:\n",
    "            cp = cp.next\n",
    "            cnt += 1\n",
    "\n",
    "        if cnt < 2:\n",
    "            return True\n",
    "\n",
    "        head = self.reverseTopN(head, cnt // 2)\n",
    "\n",
    "        slow, fast = head, head\n",
    "\n",
    "        cnt = (cnt+1)//2\n",
    "        while cnt:\n",
    "            fast = fast.next\n",
    "            cnt -= 1\n",
    "        \n",
    "        while fast:\n",
    "            if fast.val != slow.val:\n",
    "                return False\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head.next or not head:\n",
    "            return True\n",
    "        def reverse(root):\n",
    "            if not root.next:\n",
    "                return root\n",
    "            first = reverse(root.next)\n",
    "            root.next.next = root\n",
    "            root.next = None\n",
    "            return first\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        # 1 2 3 4\n",
    "        # 1 2 3 4 5\n",
    "        \n",
    "        if fast:\n",
    "            slow = slow.next\n",
    " \n",
    "        tmp = reverse(slow)\n",
    "        while tmp:\n",
    "            if tmp.val != head.val:\n",
    "                return False\n",
    "            else:\n",
    "                tmp = tmp.next\n",
    "                head = head.next\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "\n",
    "        if not head.next:\n",
    "            return True\n",
    "        \n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while fast.next and fast.next.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "\n",
    "        def reverse(node):\n",
    "            if not node or not node.next:\n",
    "                return node\n",
    "            cur = reverse(node.next)\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "            return cur\n",
    "        \n",
    "        slow.next = reverse(slow.next)\n",
    "\n",
    "        s, f = head, slow.next\n",
    "        while(f):\n",
    "            if s.val != f.val:\n",
    "                return False\n",
    "            s = s.next\n",
    "            f = f.next\n",
    "        return True\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "left=None\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        global left\n",
    "        slow,fast = head,head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        if fast!=None:\n",
    "            slow = slow.next\n",
    "        left= head\n",
    "        return self.reverse(slow)\n",
    "    def reverse(self,head):\n",
    "        global left\n",
    "        if head ==None:\n",
    "            return True\n",
    "        res = self.reverse(head.next)\n",
    "        if left and head:\n",
    "            res = res and (left.val==head.val)\n",
    "        left = left.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def reverse(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        last = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last\n",
    "\n",
    "    # def reverse(self, head: ListNode) -> ListNode:\n",
    "    #     pre, cur = None, head\n",
    "    #     while cur:\n",
    "    #         next = cur.next\n",
    "    #         cur.next = pre\n",
    "    #         pre = cur\n",
    "    #         cur = next\n",
    "    #     return pre\n",
    "\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        slow, fast = head, head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        if fast:\n",
    "            slow = slow.next\n",
    "        \n",
    "        p1 = head\n",
    "        p2 = self.reverse(slow)\n",
    "\n",
    "        while p2 != None:\n",
    "            if p1.val != p2.val:\n",
    "                return False\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    successor = None\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        cur = head\n",
    "        length = 0\n",
    "        while cur:\n",
    "            length += 1\n",
    "            cur = cur.next\n",
    "        \n",
    "        if length <= 1:\n",
    "            return True\n",
    "        cur = head\n",
    "        count = 0\n",
    "        while cur:\n",
    "            count += 1\n",
    "            if count == length//2:\n",
    "                break\n",
    "            cur = cur.next\n",
    "        h1 = cur\n",
    "        if length%2 == 0:\n",
    "            h2 = cur.next\n",
    "        else:\n",
    "            h2 = cur.next.next\n",
    "        cur.next = None\n",
    "        self.reverseTopN(head, length//2)\n",
    "        while h1 and h2:\n",
    "            if h1.val != h2.val:\n",
    "                return False\n",
    "            h1 = h1.next\n",
    "            h2 = h2.next\n",
    "        return True if h1 is None and h2 is None else False\n",
    "            \n",
    "\n",
    "    def reverseTopN(self, head, n):\n",
    "        global successor\n",
    "        if n == 1:\n",
    "            successor = head.next\n",
    "            return head\n",
    "\n",
    "        last = self.reverseTopN(head.next, n-1)\n",
    "        head.next.next = head\n",
    "        head.next = successor\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        length = 0\n",
    "        temp = head\n",
    "        while temp:\n",
    "            length += 1\n",
    "            temp = temp.next\n",
    "        return self.helper(head, length)[0]\n",
    "    def helper(self, h, l):\n",
    "        if l == 1:\n",
    "            return (True, h.next)\n",
    "        elif l == 2:\n",
    "            return (h.val == h.next.val, h.next.next)\n",
    "        temp1,temp2 = self.helper(h.next, l - 2)\n",
    "        return (h.val == temp2.val and temp1, temp2.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        p = head\n",
    "        nums = []\n",
    "        while p:\n",
    "            nums.append(p.val)\n",
    "            p = p.next\n",
    "        start,end = 0,len(nums)-1\n",
    "        print(nums)\n",
    "        def judge(start, end, nums):\n",
    "            if start == end or ( start == end -1 and nums[start] == nums[end]):\n",
    "                return True\n",
    "            if nums[start] != nums[end]:\n",
    "                return False\n",
    "            if start + 1 <= end -1:\n",
    "                return judge(start+1, end-1,nums)\n",
    "\n",
    "        return judge(0,end,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def reverse(self, head: Optional[ListNode]):\n",
    "        if head.next is None:\n",
    "            return head, head\n",
    "        re_head, re_tail = self.reverse(head=head.next)\n",
    "        head.next = None\n",
    "        re_tail.next = head\n",
    "        re_tail = re_tail.next\n",
    "        return re_head, re_tail\n",
    "\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        slow, fast = head, head\n",
    "        pre = head\n",
    "        after = ListNode(val=-1, next=None)\n",
    "        while (fast is not None) and (fast.next is not None):\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        if fast is None:\n",
    "            after, _ = self.reverse(head=slow)\n",
    "            slow = None\n",
    "        elif fast.next is None:\n",
    "            if slow.next is None:\n",
    "                return True\n",
    "            after, _ = self.reverse(head=slow.next)\n",
    "            slow = None\n",
    "\n",
    "        # 比较\n",
    "        while after is not None:\n",
    "            if pre.val != after.val:\n",
    "                return False\n",
    "            pre = pre.next\n",
    "            after = after.next\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "class ListNode:\r\n",
    "    def __init__(self, val=0, next=None):\r\n",
    "        self.val = val\r\n",
    "        self.next = next\r\n",
    "class Solution:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.successor = None\r\n",
    "\r\n",
    "    def reverseN(self, head: ListNode, n: int):\r\n",
    "        if not head or not head.next or n <= 1:\r\n",
    "            self.successor = head\r\n",
    "            return head\r\n",
    "\r\n",
    "        tmp = head.next\r\n",
    "        ret = self.reverseN(tmp, n-1)\r\n",
    "        tmp.next = head\r\n",
    "        head.next = None\r\n",
    "        return ret\r\n",
    "    \r\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\r\n",
    "        slow,fast = head,head\r\n",
    "        n = 0\r\n",
    "        while fast and fast.next:\r\n",
    "            slow = slow.next\r\n",
    "            fast = fast.next.next\r\n",
    "            n += 1\r\n",
    "        slow = slow.next if fast else slow\r\n",
    "        fast = self.reverseN(head, n)\r\n",
    "        head.next = self.successor\r\n",
    "        head = fast\r\n",
    "        while slow:\r\n",
    "            if slow.val != fast.val:\r\n",
    "                return False\r\n",
    "            slow = slow.next\r\n",
    "            fast = fast.next\r\n",
    "        \r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        def ispal(nums,left,right):\n",
    "            if left<right:\n",
    "                if nums[left]!=nums[right]:\n",
    "                    return False\n",
    "                else:\n",
    "                    return ispal(nums,left+1,right-1)\n",
    "            return True\n",
    "        res = []\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head = head.next\n",
    "        return ispal(res,0,len(res)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        # 方法一： 使用链表的前序遍历和后续遍历判断回文链表\n",
    "        self.left = head\n",
    "        res = self.traverse(head.next)\n",
    "        return res \n",
    "    \n",
    "    def traverse(self, right):\n",
    "        if right is None: return True       \n",
    "        res = self.traverse(right.next)\n",
    "        # print(right.val, self.left.val)\n",
    "        if right.val == self.left.val: \n",
    "            res = True and res \n",
    "        else:\n",
    "            res =  False\n",
    "        self.left = self.left.next\n",
    "        return res \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        self.left = head\n",
    "        return self.traverse(head)\n",
    "\n",
    "    def traverse(self, right):\n",
    "        if right == None:\n",
    "            return True\n",
    "        res = self.traverse(right.next)\n",
    "        res = res and (right.val == self.left.val)\n",
    "        self.left = self.left.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        left = low = fast = head\n",
    "        if not fast or not fast.next:\n",
    "            return True\n",
    "\n",
    "        mid = 1\n",
    "        while fast and fast.next:\n",
    "            mid += 1\n",
    "            fast = fast.next.next\n",
    "            low = low.next\n",
    "        \n",
    "        right = self.reverseFromN(head, mid)\n",
    "        while left and right:\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            left = left.next\n",
    "            right = right.next\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    # 反转给定链表，返回反转后的链表头\n",
    "    def reverse(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        tail = self.reverse(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return tail\n",
    "\n",
    "    # 从第N个节点开始，链表进行反转，返回反转后的链表头；N从1开始数\n",
    "    def reverseFromN(self, head: ListNode, n: int) -> ListNode:\n",
    "        if n == 1:\n",
    "            return self.reverse(head)\n",
    "        return self.reverseFromN(head.next, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        node = head\n",
    "        self.flag = True\n",
    "        self.memo = []\n",
    "        self.traverse(node,0)\n",
    "        return self.flag\n",
    "\n",
    "       \n",
    "\n",
    "    def traverse(self,node,idx):\n",
    "            if not node:\n",
    "                return\n",
    "            idx+=1 \n",
    "            self.memo.append(node.val)   \n",
    "            self.traverse(node.next,idx)\n",
    "            print(len(self.memo),idx)\n",
    "            if self.memo[len(self.memo)-idx]!=node.val:\n",
    "                self.flag=False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "\n",
    "        k,v = self.check(head,head)\n",
    "        return v\n",
    "        \n",
    "    def check(self,head,n):\n",
    "        if not n.next:\n",
    "            # 判断是否相等\n",
    "            return head.next,(head.val==n.val)\n",
    "\n",
    "        m,t = self.check(head,n.next)    # 进行递归\n",
    "        if t:\n",
    "            return m.next,(m.val==n.val)\n",
    "        else:\n",
    "            return \"\",False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        forward = []\n",
    "        backward = []\n",
    "        self.recursion(head, forward, backward)\n",
    "        return backward==forward\n",
    "    def recursion(self, head, forward, backward):\n",
    "        if not head:\n",
    "            return \n",
    "        forward.append(head.val)\n",
    "        self.recursion(head.next, forward, backward)\n",
    "        backward.append(head.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        left = head\n",
    "        def f(right):\n",
    "            nonlocal left\n",
    "            if right.next:\n",
    "                if not f(right.next):\n",
    "                    return False\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            left = left.next\n",
    "            return True\n",
    "        return f(head)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
    "        # 递归\n",
    "        self.prev=head\n",
    "        def recursive(head):\n",
    "            if not head:\n",
    "                return True\n",
    "            if not recursive(head.next):\n",
    "                return False\n",
    "            if head.val!=self.prev.val:\n",
    "                return False\n",
    "            self.prev=self.prev.next\n",
    "            return True\n",
    "        return recursive(head)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "        # 递归\n",
    "        self.newHead = head\n",
    "        def check(cur = head):\n",
    "            if cur is not None:\n",
    "                if not check(cur.next):\n",
    "                    return False\n",
    "                if self.newHead.val != cur.val:\n",
    "                    return False\n",
    "                self.newHead = self.newHead.next\n",
    "            return True\n",
    "        return check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, head: ListNode) -> bool:\n",
    "\n",
    "        self.front_pointer = head\n",
    "\n",
    "        def recursively_check(current_node=head):\n",
    "            if current_node is not None:\n",
    "                if not recursively_check(current_node.next):\n",
    "                    return False\n",
    "                if self.front_pointer.val != current_node.val:\n",
    "                    return False\n",
    "                self.front_pointer = self.front_pointer.next\n",
    "            return True\n",
    "\n",
    "        return recursively_check()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        a = str(x)\n",
    "        b = [a[n] for n in range(len(a))]\n",
    "        c = [a[n] for n in range(len(a)-1,-1,-1)]\n",
    "        return b == c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: 'int') -> 'bool': \n",
    "        s1 = str(x)\n",
    "        print(s1)\n",
    "        l = list(s1)\n",
    "        print(l)\n",
    "        for i in range(0, int(len(l) / 2)):\n",
    "            if l[i] == l[-1 - i]:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: 'int') -> 'bool':\n",
    "        new_x = 0\n",
    "        old_x = x\n",
    "        if x<0:\n",
    "            return False\n",
    "        while x!=0:\n",
    "            l = x%10\n",
    "            x = int(x/10)\n",
    "            new_x = new_x*10+l\n",
    "        print(new_x, old_x)\n",
    "        if new_x==old_x:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #return  x>=0 and str(x)[:len(str(x))//2]== str(x)[len(str(x))-1:(len(str(x))-1)//2:-1]\n",
    "        \n",
    "        # x= str(x)\n",
    "        # start = 0\n",
    "        # end = len(x)-1\n",
    "        # while x[start]==x[end]:\n",
    "        #     start = start+1\n",
    "        #     end = end -1\n",
    "        #     if start>=end:\n",
    "        #         return True\n",
    "        # return False\n",
    "        \n",
    "        # if x >= 0 and x < 10:\n",
    "        #     return True\n",
    "        # elif x < 0 or x % 10 == 0:\n",
    "        #     return False\n",
    "        # else:\n",
    "        #     number, reversed_number = x, 0\n",
    "        #     while (number > 0):    #remove the last digit and append it to the end of reverse\n",
    "        #         last_digit = number % 10   #isolate the last digit number\n",
    "        #         reversed_number = (reversed_number * 10) + last_digit   #append it to end of reverse\n",
    "        #         number = int(number / 10)   #remove it from the number\n",
    "        #     return x == reversed_number\n",
    "        return  x>=0 and str(x)[::-1]== str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #return  x>=0 and str(x)[:len(str(x))//2]== str(x)[len(str(x))-1:(len(str(x))-1)//2:-1]\n",
    "        \n",
    "        # x= str(x)\n",
    "        # start = 0\n",
    "        # end = len(x)-1\n",
    "        # while x[start]==x[end]:\n",
    "        #     start = start+1\n",
    "        #     end = end -1\n",
    "        #     if start>=end:\n",
    "        #         return True\n",
    "        # return False\n",
    "        \n",
    "        if x >= 0 and x < 10:\n",
    "            return True\n",
    "        elif x < 0 or x % 10 == 0:\n",
    "            return False\n",
    "        else:\n",
    "            number, reversed_number = x, 0\n",
    "            while (number > 0):    #remove the last digit and append it to the end of reverse\n",
    "                last_digit = number % 10   #isolate the last digit number\n",
    "                reversed_number = (reversed_number * 10) + last_digit   #append it to end of reverse\n",
    "                number = int(number / 10)   #remove it from the number\n",
    "            return x == reversed_number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: 'int') -> 'bool':\n",
    "        s=str(x)\n",
    "       \n",
    "        def huiwen(s,l,r):\n",
    "            if l>r or l==r:\n",
    "                if s[l]==s[r]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if s[l]==s[r]:\n",
    "                    return True and huiwen(s,l+1,r-1)\n",
    "                else:\n",
    "                    return False\n",
    "        return huiwen(s,0,len(s)-1)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        s=str(x)\n",
    "        c=list(s)\n",
    "        d=list(reversed(s))\n",
    "        return c==d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x < 0:\n",
    "            return False\n",
    "        else:\n",
    "            y = str(x)[::-1]\n",
    "            if y == str(x):\n",
    "                return True\n",
    "            else: \n",
    "                return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #if x< 0:\n",
    "            #return False\n",
    "        x_str = list(str(x))\n",
    "        for i in range(len(x_str)//2):\n",
    "            print(i)\n",
    "            if not x_str[i] == x_str[len(x_str)-1-i]:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        sum=0\n",
    "        if x<0:\n",
    "            return bool(0)\n",
    "        s=str(x)\n",
    "        l=len(s)\n",
    "        if l==1:\n",
    "            return bool(1)\n",
    "        length=l//2\n",
    "        for i in list(range(length)):\n",
    "            print(s[i])\n",
    "            print(s[-(i+1)])\n",
    "            if s[i]!=s[-(i+1)]:\n",
    "                return bool(0)\n",
    "            else:\n",
    "                sum=sum+1\n",
    "        if sum==length:\n",
    "            return bool(1)     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #s = str(x)[::-1]\n",
    "        return str(x)[::-1] == str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if x<0:return False\n",
    "        \n",
    "        temp=int(str(x)[::-1])\n",
    "        \n",
    "        return temp==x\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if x < 0:\n",
    "            return False\n",
    "        else:\n",
    "            y = str(x)[::-1]\n",
    "            if y == str(x):\n",
    "                return True\n",
    "            else: \n",
    "                return False\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x < 0:\n",
    "            return False\n",
    "        \n",
    "        x_list = []\n",
    "        while x != 0:\n",
    "            x_list.append(x % 10)\n",
    "            x = x // 10\n",
    "        \n",
    "        return x_list == x_list[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        str_x = str(x)\n",
    "        for i in range(0, int(len(str_x)/2)):\n",
    "            if str_x[i] != str_x[-i-1]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x < 10 and x >= 0:\n",
    "            return True\n",
    "        if x < 0 or x % 10 == 0:\n",
    "            return False\n",
    "        new_x = 0\n",
    "        # i = 0\n",
    "        while x > new_x:\n",
    "            # i += 1\n",
    "            new_x *= 10\n",
    "            new_x += x % 10\n",
    "            x //= 10\n",
    "        if x == new_x or x == new_x // 10:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        lst = list(str(x))\n",
    "        while len(lst) > 1:\n",
    "            if lst.pop(0) != lst.pop():\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x<0:\n",
    "            return False\n",
    "        else:\n",
    "            return str(x) ==str(x)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        s=str(x)\n",
    "        i,j=0,len(s)-1\n",
    "        while i<j:\n",
    "            if s[i]==s[j]:\n",
    "                i+=1\n",
    "                j-=1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        a=str(x).split('-')\n",
    "        if len(a)>1:\n",
    "            return False\n",
    "        else:\n",
    "            b=a[0][::-1]\n",
    "            if a[0]==b:\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        return str(x) == str(x)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        r = x\n",
    "        if x<0:\n",
    "            return False\n",
    "        # stack = []\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        while x>0:\n",
    "            t = x%10\n",
    "            print(t)\n",
    "            # stack.append(t)\n",
    "            ans = ans*10 + t\n",
    "            print(ans)\n",
    "            cnt+=1\n",
    "            x = x//10\n",
    "            print(x)\n",
    "        # print(ans,r)\n",
    "        if ans == r:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        # c = 0\n",
    "        # print(ans)\n",
    "        # for i in range(len(stack)):\n",
    "        #     c += 10**(len(stack)-1-i)*stack[i]\n",
    "        # print(stack,c)\n",
    "        # if c == r:\n",
    "        #     return True\n",
    "        # else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x<0:\n",
    "            return False\n",
    "        num = list(str(x))\n",
    "        len_num=len(num)\n",
    "        \n",
    "        for i in range(len_num//2+1):\n",
    "            print(num[i])\n",
    "            if num[i] != num[len_num-i-1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x <0  :\n",
    "            res = False\n",
    "        elif x <10 or x ==0:\n",
    "            res = True\n",
    "        else:\n",
    "            stry = ''.join(str(x))\n",
    "            l = len(stry)\n",
    "            v = l //2\n",
    "\n",
    "            for i in range(v):\n",
    "                print(i)\n",
    "                j = -1*(i+1)\n",
    "                print(stry[i],stry[j])\n",
    "                if stry[i] ==stry[j]:\n",
    "                    res = True\n",
    "                else:\n",
    "                    res = False\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "         x = str(x)\n",
    "         if x == x[::-1]:\n",
    "             return True\n",
    "         else:\n",
    "             return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if str(x)[:] == str(x)[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        x = str(x)\n",
    "        return x == x[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        a=str(x)\n",
    "        for i in range(0,int(len(a)/2)):\n",
    "            if a[i]!=a[len(a)-i-1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x < 0:\n",
    "            return False\n",
    "        if x == 0:\n",
    "            return True\n",
    "        \n",
    "        n = 1 + int(log(x, 10))  # x 的位数是 n\n",
    "        for i in range(0,int(n/2)):\n",
    "            a = (x // 10**(n-i-1)) % 10   # 提取第 i+1 位的数字\n",
    "            b = (x // 10**i) % 10    # 提取倒数第 i+1 位数\n",
    "            print(a,b)\n",
    "            if a != b:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x < 0:\n",
    "            return False\n",
    "        l = len(str(x))-1\n",
    "        c = str(x)\n",
    "        i = 0\n",
    "        while (i < l):\n",
    "            print(i)\n",
    "            print(l)\n",
    "            if c[i] == c[l]:\n",
    "                i = i + 1\n",
    "                l = l - 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        return str(x) == str(x)[::-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        return str(x) == str(x)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if str(x) == str(x)[::-1]:\n",
    "            result = True\n",
    "            return result\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
